package com.my.collection.graph.v2;

import com.my.collection.graph.v1.ElementExistException;
import com.my.collection.graph.v1.ElementNotFoundException;
import com.my.collection.graph.v1.Stack;

import java.util.*;

/**
 * Created by ZhongGang
 * at 2018/10/22 11:02
 * <p>
 * 有向非加权图
 */
public class Graph<V> {
    private Map<V, Set<V>> table = new HashMap<>();

    public Graph() {
    }

    /**
     * 添加顶点
     *
     * @param v
     */
    public void addVertex(V v) {
        if (this.table.containsKey(v)) {
            throw new ElementExistException();
        }

        this.table.put(v, new HashSet<>());
    }

    /**
     * 连接两个顶点，即为两个顶点添加一条边
     *
     * @param from
     * @param to
     */
    public void addEdge(V from, V to) {
        if (!this.table.containsKey(from) || !this.table.containsKey(to)) {
            throw new ElementNotFoundException();
        }

        this.table.get(from).add(to);
    }

    /**
     * 返回图的所有顶点
     *
     * @return
     */
    public List<V> vertexes() {
        return new ArrayList<>(this.table.keySet());
    }

    /**
     * 有向无环图（DAG）的拓扑排序，基于深度遍历
     * <p>
     * 后序排序结果的倒排
     *
     * @param v
     * @return
     */
    public List<V> topologySort(V v) {
        List<V> visited = new ArrayList<>();
        List<V> topology = new ArrayList<>();
        topologySort(visited, topology, v);
        Collections.reverse(topology);//后序排序结果的倒排
        return topology;
    }

    private void topologySort(List<V> visited, List<V> topology, V v) {
        visited.add(v);

        Set<V> vs = this.table.get(v);
        for (V v1 : vs) {
            if (!visited.contains(v1)) {
                topologySort(visited, topology, v1);
            }
        }

        topology.add(v);
    }

    /**
     * 有向无环图（DAG）的前序排序，基于深度遍历
     *
     * @param v
     * @return
     */
    public List<V> preOrder(V v) {
        List<V> visited = new ArrayList<>();
        List<V> preOrder = new ArrayList<>();
        preOrder(visited, preOrder, v);
        return preOrder;
    }

    private void preOrder(List<V> visited, List<V> preOrder, V v) {
        preOrder.add(v);
        visited.add(v);

        Set<V> vs = this.table.get(v);
        for (V v1 : vs) {
            if (!visited.contains(v1)) {
                preOrder(visited, preOrder, v1);
            }
        }
    }

    /**
     * 有向无环图（DAG）的后序排序，基于深度遍历
     *
     * @param v
     * @return
     */
    public List<V> postOrder(V v) {
        List<V> visited = new ArrayList<>();
        List<V> postOrder = new ArrayList<>();
        postOrder(visited, postOrder, v);
        return postOrder;
    }

    private void postOrder(List<V> visited, List<V> postOrder, V v) {
        visited.add(v);

        Set<V> vs = this.table.get(v);
        for (V v1 : vs) {
            if (!visited.contains(v1)) {
                postOrder(visited, postOrder, v1);
            }
        }

        postOrder.add(v);
    }

    /**
     * 两个给定顶点间是否存在至少一条连通的路径
     *
     * @param from
     * @param to
     * @return
     */
    public boolean hasPath(V from, V to) {
        if (!this.table.containsKey(from) || !this.table.containsKey(to)) {
            throw new ElementNotFoundException();
        }

        List<V> visited = new ArrayList<>();
        Stack<V> stack = new Stack<>();
        stack.push(from);
        while (!stack.isEmpty()) {
            V pop = stack.pop();
            if (!visited.contains(pop)) {
                visited.add(pop);
            }

            Set<V> vs = this.table.get(pop);
            for (V v1 : vs) {
                if (Objects.equals(v1, to)) {
                    return true;
                } else {
                    if (!visited.contains(v1)) {
                        stack.push(v1);
                    }
                }
            }
        }
        return false;
    }

    /**
     * 两个给定顶点间的一条连通的路径
     *
     * @param from
     * @param to
     * @return
     */
    public List<V> path(V from, V to) {
        if (!this.table.containsKey(from) || !this.table.containsKey(to)) {
            throw new ElementNotFoundException();
        }

        java.util.Stack<V> stack = new java.util.Stack<>();
        stack.push(from);
        Map<V, Set<V>> visitedEdges = new HashMap<>();
        while (!stack.isEmpty()) {
            V peek = stack.peek();

            if (!visitedEdges.containsKey(peek)) {
                visitedEdges.put(peek, new HashSet<>());
            }

            Set<V> vs = this.table.get(peek);
            if (visitedEdges.get(peek).size() == vs.size()) {
                V pop = stack.pop();
                visitedEdges.remove(pop);
            } else {
                for (V v : vs) {
                    if (!visitedEdges.get(peek).contains(v)) {
                        stack.push(v);
                        visitedEdges.get(peek).add(v);

                        if (Objects.equals(v, to)) {
                            ArrayList<V> path = new ArrayList<>(stack);
                            stack.pop();
                            return path;
                        }

                        break;
                    }
                }
            }
        }
        return new ArrayList<>();
    }

    /**
     * 两个给定顶点间的所有连通的路径
     *
     * @param from
     * @param to
     * @return
     */
    public List<List<V>> paths(V from, V to) {
        if (!this.table.containsKey(from) || !this.table.containsKey(to)) {
            throw new ElementNotFoundException();
        }

        List<List<V>> paths = new ArrayList<>();
        java.util.Stack<V> stack = new java.util.Stack<>();
        stack.push(from);
        Map<V, Set<V>> visitedEdges = new HashMap<>();
        while (!stack.isEmpty()) {
            V peek = stack.peek();

            if (!visitedEdges.containsKey(peek)) {
                visitedEdges.put(peek, new HashSet<>());
            }

            Set<V> vs = this.table.get(peek);
            if (visitedEdges.get(peek).containsAll(vs)) {
                V pop = stack.pop();
                visitedEdges.remove(pop);
            } else {
                for (V v : vs) {
                    if (!visitedEdges.get(peek).contains(v)) {
                        stack.push(v);
                        visitedEdges.get(peek).add(v);

                        if (Objects.equals(v, to)) {
                            paths.add(new ArrayList<>(stack));
                            stack.pop();
                        }

                        break;
                    }
                }
            }
        }
        return paths;
    }
}
